{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "\n",
    "\n",
    "## 前向传播\n",
    "\n",
    "  参考 [卷积层的反向传播-多通道、无padding、步长1](0_2_4-卷积层的反向传播-多通道、有padding、步长不为1.md)中公式(4) \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def conv_forward(z, K, b, padding=(0, 0), strides=(1, 1)):\n",
    "    \"\"\"\n",
    "    多通道卷积前向过程\n",
    "    :param z: 卷积层矩阵,形状(N,C,H,W)，N为batch_size，C为通道数\n",
    "    :param K: 卷积核,形状(C,D,k1,k2), C为输入通道数，D为输出通道数\n",
    "    :param b: 偏置,形状(D,)\n",
    "    :param padding: padding\n",
    "    :param strides: 步长\n",
    "    :return: 卷积结果\n",
    "    \"\"\"\n",
    "    padding_z = np.lib.pad(z, ((0, 0), (0, 0), (padding[0], padding[0]), (padding[1], padding[1])), 'constant', constant_values=0)\n",
    "    N, _, height, width = padding_z.shape\n",
    "    C, D, k1, k2 = K.shape\n",
    "    assert (height - k1) % strides[0] == 0, '步长不为1时，步长必须刚好能够被整除'\n",
    "    assert (width - k2) % strides[1] == 0, '步长不为1时，步长必须刚好能够被整除'\n",
    "    conv_z = np.zeros((N, D, 1 + (height - k1) // strides[0], 1 + (width - k2) // strides[1]))\n",
    "    for n in np.arange(N):\n",
    "        for d in np.arange(D):\n",
    "            for h in np.arange(height - k1 + 1)[::strides[0]]:\n",
    "                for w in np.arange(width - k2 + 1)[::strides[1]]:\n",
    "                    conv_z[n, d, h // strides[0], w // strides[1]] = np.sum(padding_z[n, :, h:h + k1, w:w + k2] * K[:, d]) + b[d]\n",
    "    return conv_z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 反向传播\n",
    " \n",
    " \n",
    "参考[卷积层的反向传播-多通道、无padding、步长1](0_2_4-卷积层的反向传播-多通道、有padding、步长不为1.md)中公式(5),(6)和(9) \n",
    "  \n",
    "首先定义两个内部函数,一个是在反向中对于步长大于1的卷积核,对输出层梯度行列(高度和宽宽)之间插入零;另一个是对于padding不为零的卷积核，在对输入层求梯度后，剔除padding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def _insert_zeros(dz, strides):\n",
    "    \"\"\"\n",
    "    想多维数组最后两位，每个行列之间增加指定的个数的零填充\n",
    "    :param dz: (N,D,H,W),H,W为卷积输出层的高度和宽度\n",
    "    :param strides: 步长\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    _, _, H, W = dz.shape\n",
    "    pz = dz\n",
    "    if strides[0] > 1:\n",
    "        for h in np.arange(H - 1, 0, -1):\n",
    "            for o in np.arange(strides[0] - 1):\n",
    "                pz = np.insert(pz, h, 0, axis=2)\n",
    "    if strides[1] > 1:\n",
    "        for w in np.arange(W - 1, 0, -1):\n",
    "            for o in np.arange(strides[1] - 1):\n",
    "                pz = np.insert(pz, w, 0, axis=3)\n",
    "    return pz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def _remove_padding(z, padding):\n",
    "    \"\"\"\n",
    "    移除padding\n",
    "    :param z: (N,C,H,W)\n",
    "    :param paddings: (p1,p2)\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    if padding[0] > 0 and padding[1] > 0:\n",
    "        return z[:, :, padding[0]:-padding[0], padding[1]:-padding[1]]\n",
    "    elif padding[0] > 0:\n",
    "        return z[:, :, padding[0]:-padding[0], :]\n",
    "    elif padding[1] > 0:\n",
    "        return z[:, :, :, padding[1]:-padding[1]]\n",
    "    else:\n",
    "        return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def conv_backward(next_dz, K, z, padding=(0, 0), strides=(1, 1)):\n",
    "    \"\"\"\n",
    "    多通道卷积层的反向过程\n",
    "    :param next_dz: 卷积输出层的梯度,(N,D,H',W'),H',W'为卷积输出层的高度和宽度\n",
    "    :param K: 当前层卷积核，(C,D,k1,k2)\n",
    "    :param z: 卷积层矩阵,形状(N,C,H,W)，N为batch_size，C为通道数\n",
    "    :param padding: padding\n",
    "    :param strides: 步长\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    N, C, H, W = z.shape\n",
    "    C, D, k1, k2 = K.shape\n",
    "\n",
    "    # 卷积核梯度\n",
    "    # dK = np.zeros((C, D, k1, k2))\n",
    "    padding_next_dz = _insert_zeros(next_dz, strides)\n",
    "\n",
    "    # 卷积核高度和宽度翻转180度\n",
    "    flip_K = np.flip(K, (2, 3))\n",
    "    # 交换C,D为D,C；D变为输入通道数了，C变为输出通道数了\n",
    "    swap_flip_K = np.swapaxes(flip_K, 0, 1)\n",
    "    # 增加高度和宽度0填充\n",
    "    ppadding_next_dz = np.lib.pad(padding_next_dz, ((0, 0), (0, 0), (k1 - 1, k1 - 1), (k2 - 1, k2 - 1)), 'constant', constant_values=0)\n",
    "    dz = conv_forward(ppadding_next_dz.astype(np.float64), swap_flip_K.astype(np.float64), np.zeros((C,), dtype=np.float64))\n",
    "\n",
    "    # 求卷积核的梯度dK\n",
    "    swap_z = np.swapaxes(z, 0, 1)  # 变为(C,N,H,W)与\n",
    "    dK = conv_forward(swap_z.astype(np.float64), padding_next_dz.astype(np.float64), np.zeros((D,), dtype=np.float64))\n",
    "\n",
    "    # 偏置的梯度\n",
    "    db = np.sum(np.sum(np.sum(next_dz, axis=-1), axis=-1), axis=0)  # 在高度、宽度上相加；批量大小上相加\n",
    "\n",
    "    # 把padding减掉\n",
    "    dz = _remove_padding(dz, padding)  # dz[:, :, padding[0]:-padding[0], padding[1]:-padding[1]]\n",
    "\n",
    "    return dK / N, db / N, dz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "说明：\n",
    "a)求卷积核的梯度dk时，输出就是维度是卷积核的维度(C,D,k1,k2),卷积核是输出层的梯度，其维度为(N,D,H',W'),而输入z的维度是(N,C,H,W);这样是无法做卷积的，需要对输入z在做坐标轴交换变为(C,N,H,W)\n",
    "b)求输入层的梯度dz时，需要最后将padding去除"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  测试卷积\n",
    "\n",
    "   以下实现一个简单的卷积层,输入为随机数组成的多维向量，训练前向反向过程，使得输出为数值全为1的多维向量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 随机初始化输入及卷积核和偏置\n",
    "z = np.random.randn(3, 3, 28, 28).astype(np.float64)\n",
    "K = np.random.randn(3, 4, 3, 3).astype(np.float64) \n",
    "b = np.zeros(4).astype(np.float64)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "设目标输出是全为1的多维向量,第一维是批量、第二维是通道、最后两维是高度和宽度"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 没有padding,输入的高度和宽度是28*28,卷积核是3*3,输出高度和宽度就是28-3+1=26\n",
    "y_true = np.ones((3,4,26,26))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用均方差测试训练结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step:0,loss:958.5152318628079\n",
      "step:1,loss:114.23165466757392\n",
      "step:2,loss:16.9234502274236\n",
      "step:3,loss:2.903057803363628\n",
      "step:4,loss:0.5504744425822835\n",
      "step:5,loss:0.11178474540749396\n",
      "step:6,loss:0.02379679311685128\n",
      "step:7,loss:0.005236389076545019\n",
      "step:8,loss:0.001180098339494189\n",
      "step:9,loss:0.0002707210063947661\n",
      "step:10,loss:6.295634504463701e-05\n",
      "step:11,loss:1.479818044078476e-05\n",
      "step:12,loss:3.5084607011387207e-06\n",
      "step:13,loss:8.37695810893191e-07\n",
      "step:14,loss:2.0118706827119602e-07\n",
      "step:15,loss:4.855726068963752e-08\n",
      "step:16,loss:1.176869018912479e-08\n",
      "step:17,loss:2.8626182548592072e-09\n",
      "step:18,loss:6.984720164126196e-10\n",
      "step:19,loss:1.7088760886434073e-10\n",
      "step:20,loss:4.190856797521701e-11\n",
      "yes\n"
     ]
    }
   ],
   "source": [
    "from nn.losses import mean_squared_loss\n",
    "for i in range(1000):\n",
    "    # 前向\n",
    "    next_z = conv_forward(z, K, b)\n",
    "    # 反向\n",
    "    loss, dy = mean_squared_loss(next_z, y_true)\n",
    "    dK, db, _ = conv_backward(dy, K, z)\n",
    "    # 更新梯度\n",
    "    K -= 0.001 * dK\n",
    "    b -= 0.001 * db\n",
    "\n",
    "    # 打印损失\n",
    "    print(\"step:{},loss:{}\".format(i, loss))\n",
    "\n",
    "    if np.allclose(y_true, next_z):\n",
    "        print(\"yes\")\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到经过很少的十几步迭代就收敛了，下面来看看训练后输出结果,可以看到结果已经很接近1了;说卷积层的前向后向过程是正确的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "min:0.9999936935628233,max:1.0000059630060474,avg:0.999999847110127\n"
     ]
    }
   ],
   "source": [
    "print(\"min:{},max:{},avg:{}\".format(np.min(next_z),np.max(next_z),np.average(next_z)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cython加速\n",
    "\n",
    "对于卷积层的前向过程使用Cython编译加速,实际测试发现耗时减少约20%,貌似提升效果不大;对Cython使用不精通，哪位大佬知道如何改进，请不吝赐教，感谢！！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%load_ext Cython"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n",
      "Error compiling Cython file:\n",
      "------------------------------------------------------------\n",
      "...\n",
      "    :param b: 偏置,形状(D,)\n",
      "    :param padding: padding\n",
      "    :param strides: 步长\n",
      "    :return: 卷积结果\n",
      "    \"\"\"\n",
      "    cdef np.ndarray[double, ndim= 4] padding_z = np.lib.pad(z, ((0, 0), (0, 0), (padding[0], padding[0]),\n",
      "                                                  ^\n",
      "------------------------------------------------------------\n",
      "\n",
      "C:\\Users\\mick.yi\\.ipython\\cython\\_cython_magic_fb0c9faf27820f55ef5f1be4f3a8bdce.pyx:17:51: cimported module has no attribute 'lib'\n",
      "\n",
      "Error compiling Cython file:\n",
      "------------------------------------------------------------\n",
      "...\n",
      "    cdef unsigned int s0 = strides[0]\n",
      "    cdef unsigned int s1 = strides[1]\n",
      "\n",
      "    assert (height - k1) % s0 == 0, '步长不为1时，步长必须刚好能够被整除'\n",
      "    assert (width - k2) % s1 == 0, '步长不为1时，步长必须刚好能够被整除'\n",
      "    cdef np.ndarray[double, ndim= 4] conv_z = np.zeros((N, D, 1 + (height - k1) // s0, 1 + (width - k2) // s1))\n",
      "                                               ^\n",
      "------------------------------------------------------------\n",
      "\n",
      "C:\\Users\\mick.yi\\.ipython\\cython\\_cython_magic_fb0c9faf27820f55ef5f1be4f3a8bdce.pyx:33:48: cimported module has no attribute 'zeros'\n",
      "\n",
      "Error compiling Cython file:\n",
      "------------------------------------------------------------\n",
      "...\n",
      "\n",
      "    assert (height - k1) % s0 == 0, '步长不为1时，步长必须刚好能够被整除'\n",
      "    assert (width - k2) % s1 == 0, '步长不为1时，步长必须刚好能够被整除'\n",
      "    cdef np.ndarray[double, ndim= 4] conv_z = np.zeros((N, D, 1 + (height - k1) // s0, 1 + (width - k2) // s1))\n",
      "    cdef unsigned int n, d, h, w\n",
      "    for n in np.arange(N):\n",
      "              ^\n",
      "------------------------------------------------------------\n",
      "\n",
      "C:\\Users\\mick.yi\\.ipython\\cython\\_cython_magic_fb0c9faf27820f55ef5f1be4f3a8bdce.pyx:35:15: cimported module has no attribute 'arange'\n",
      "\n",
      "Error compiling Cython file:\n",
      "------------------------------------------------------------\n",
      "...\n",
      "    assert (height - k1) % s0 == 0, '步长不为1时，步长必须刚好能够被整除'\n",
      "    assert (width - k2) % s1 == 0, '步长不为1时，步长必须刚好能够被整除'\n",
      "    cdef np.ndarray[double, ndim= 4] conv_z = np.zeros((N, D, 1 + (height - k1) // s0, 1 + (width - k2) // s1))\n",
      "    cdef unsigned int n, d, h, w\n",
      "    for n in np.arange(N):\n",
      "        for d in np.arange(D):\n",
      "                  ^\n",
      "------------------------------------------------------------\n",
      "\n",
      "C:\\Users\\mick.yi\\.ipython\\cython\\_cython_magic_fb0c9faf27820f55ef5f1be4f3a8bdce.pyx:36:19: cimported module has no attribute 'arange'\n",
      "\n",
      "Error compiling Cython file:\n",
      "------------------------------------------------------------\n",
      "...\n",
      "    assert (width - k2) % s1 == 0, '步长不为1时，步长必须刚好能够被整除'\n",
      "    cdef np.ndarray[double, ndim= 4] conv_z = np.zeros((N, D, 1 + (height - k1) // s0, 1 + (width - k2) // s1))\n",
      "    cdef unsigned int n, d, h, w\n",
      "    for n in np.arange(N):\n",
      "        for d in np.arange(D):\n",
      "            for h in np.arange(height - k1 + 1)[::s0]:\n",
      "                      ^\n",
      "------------------------------------------------------------\n",
      "\n",
      "C:\\Users\\mick.yi\\.ipython\\cython\\_cython_magic_fb0c9faf27820f55ef5f1be4f3a8bdce.pyx:37:23: cimported module has no attribute 'arange'\n",
      "\n",
      "Error compiling Cython file:\n",
      "------------------------------------------------------------\n",
      "...\n",
      "    cdef np.ndarray[double, ndim= 4] conv_z = np.zeros((N, D, 1 + (height - k1) // s0, 1 + (width - k2) // s1))\n",
      "    cdef unsigned int n, d, h, w\n",
      "    for n in np.arange(N):\n",
      "        for d in np.arange(D):\n",
      "            for h in np.arange(height - k1 + 1)[::s0]:\n",
      "                for w in np.arange(width - k2 + 1)[::s1]:\n",
      "                          ^\n",
      "------------------------------------------------------------\n",
      "\n",
      "C:\\Users\\mick.yi\\.ipython\\cython\\_cython_magic_fb0c9faf27820f55ef5f1be4f3a8bdce.pyx:38:27: cimported module has no attribute 'arange'\n",
      "\n",
      "Error compiling Cython file:\n",
      "------------------------------------------------------------\n",
      "...\n",
      "    cdef unsigned int n, d, h, w\n",
      "    for n in np.arange(N):\n",
      "        for d in np.arange(D):\n",
      "            for h in np.arange(height - k1 + 1)[::s0]:\n",
      "                for w in np.arange(width - k2 + 1)[::s1]:\n",
      "                    conv_z[n, d, h // s0, w // s1] = np.sum(padding_z[n, :, h:h + k1, w:w + k2] * K[:, d]) + b[d]\n",
      "                                                      ^\n",
      "------------------------------------------------------------\n",
      "\n",
      "C:\\Users\\mick.yi\\.ipython\\cython\\_cython_magic_fb0c9faf27820f55ef5f1be4f3a8bdce.pyx:39:55: cimported module has no attribute 'sum'\n"
     ]
    }
   ],
   "source": [
    "%%cython\n",
    "cimport cython\n",
    "cimport numpy as np\n",
    "cpdef conv_forward(np.ndarray[double, ndim=4] z,\n",
    "                   np.ndarray[double, ndim=4] K,\n",
    "                   np.ndarray[double, ndim=1] b,\n",
    "                   tuple padding=(0, 0),\n",
    "                   tuple strides=(1, 1)):\n",
    "    \"\"\"\n",
    "    多通道卷积前向过程\n",
    "    :param z: 卷积层矩阵,形状(N,C,H,W)，N为batch_size，C为通道数\n",
    "    :param K: 卷积核,形状(C,D,k1,k2), C为输入通道数，D为输出通道数\n",
    "    :param b: 偏置,形状(D,)\n",
    "    :param padding: padding\n",
    "    :param strides: 步长\n",
    "    :return: 卷积结果\n",
    "    \"\"\"\n",
    "    cdef np.ndarray[double, ndim= 4] padding_z = np.lib.pad(z, ((0, 0), (0, 0), (padding[0], padding[0]),\n",
    "                                                                 (padding[1], padding[1])), 'constant', constant_values=0)\n",
    "    cdef unsigned int N = padding_z.shape[0]\n",
    "    cdef unsigned int height = padding_z.shape[2]\n",
    "    cdef unsigned int  width = padding_z.shape[3]\n",
    "    cdef unsigned int C = K.shape[0]\n",
    "    cdef unsigned int D = K.shape[1]\n",
    "\n",
    "    cdef unsigned int k1 = K.shape[2]\n",
    "    cdef unsigned int k2 = K.shape[3]\n",
    "\n",
    "    cdef unsigned int s0 = strides[0]\n",
    "    cdef unsigned int s1 = strides[1]\n",
    "\n",
    "    assert (height - k1) % s0 == 0, '步长不为1时，步长必须刚好能够被整除'\n",
    "    assert (width - k2) % s1 == 0, '步长不为1时，步长必须刚好能够被整除'\n",
    "    cdef np.ndarray[double, ndim= 4] conv_z = np.zeros((N, D, 1 + (height - k1) // s0, 1 + (width - k2) // s1))\n",
    "    cdef unsigned int n, d, h, w\n",
    "    for n in np.arange(N):\n",
    "        for d in np.arange(D):\n",
    "            for h in np.arange(height - k1 + 1)[::s0]:\n",
    "                for w in np.arange(width - k2 + 1)[::s1]:\n",
    "                    conv_z[n, d, h // s0, w // s1] = np.sum(padding_z[n, :, h:h + k1, w:w + k2] * K[:, d]) + b[d]\n",
    "\n",
    "    return conv_z"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
